The present invention relates to digital image processing.
The following U.S. Patents have been found in a U.S. Patent Search and are believed to be generally relevant to the field of the invention:
Digital photographs with extended fields of view are conventionally created using an image processing technique known as xe2x80x9cstitchingxe2x80x9d, wherein a user takes multiple photographic images using a camera and rotates the camera between images, so as to produce overlapping photos spanning an entire vista. A xe2x80x9cstitcherxe2x80x9d then combines the various images into a single large xe2x80x9comniviewxe2x80x9d image with an extended field of view, up to a full 360xc2x0. The stitching process itself involves various steps, such as correction of the images for camera angle and tilt, image alignment between successive images to account for overlap, and texture mapping. When performed accurately and properly viewed with appropriate perspective correction, the resulting large image gives the viewer the experience of being immersed within a vista.
Although certain professional lenses, such as fisheye lenses, are capable of photographing an entire hemispherical view as a single image, use of a stitcher enables a non-professional photographer to use a standard lens, and yet capture the same extended wide angle view. The computational processing within the stitcher effectively carries out necessary three-dimensional geometrical transformations to account for the non-linear distortion in a wide angle view. Specifically, it projects the various linear images onto the surface of a sphere or cylinder or cubexe2x80x94depending on a desired environment map.
One commonly encountered source of artifacts in stitching is the variable lighting of individual images. As the camera rotates, for example, one image can be taken into the sun, and thus deviate from the other images with respect to lighting. When this image is stitched with the others, it stands out awkwardly.
Current state of the art stitchers use a process known as xe2x80x9cfeatheringxe2x80x9d to merge together a left image (hereinafter designated as xe2x80x9cimage Axe2x80x9d) and an adjacent right image (hereinafter designated xe2x80x9cimage Bxe2x80x9d). Typical implementations of feathering operate after the images are aligned and the overlap region has been identified. They then feather the two images within the overlap region, by weighted combining using weights which vary from a value above 50% (e.g. 100%) of image A and a value below 50% (e.g. 0%) image B at the left side of the overlap region, to a value below 50% (e.g. 0%) of image A and a value above 50% (e.g. 100%) of image B at the right side of the overlap region. However, if the lighting conditions of the two images are substantially at variance and the overlap region is narrow, this technique of feathering does not work well, and typically produces noticeable bands at the overlap region. This is to be expected, since feathering does not affect pixel color values outside of the overlapping region.
Another common artifact, referred to as xe2x80x9cghosting,xe2x80x9d occurs when two images being blended together are slightly misaligned. Suppose, for example, that the overlap region contains a bright square of dimensions 1xe2x80x3xc3x971xe2x80x3. If the two images are mis-aligned horizontally by 0.1xe2x80x3, then feathering will produce an elongated square (i.e. a rectangle) of dimensions 1.1xe2x80x3xc3x971xe2x80x3. Moreover the leftmost and rightmost strips of the rectangle, of dimensions 0.1xe2x80x3xc3x971xe2x80x3, will be less bright than the rest of the rectangle. The appearance of these less bright strips at the left and right ends of the rectangle gives the effect of ghosting, whereby only a partial remnant of the square is present. It should be emphasized that alignment is practically never perfect, and as such, there is always some form of ghosting present.
Another source of ghosting occurs when an object is present in one of the images and absent in the other. For example, a person might appear in image A and be absent from image B, having moved out of sight between the times the two images were photographed.
The present invention provides a novel approach to image feathering of two overlapping images (hereinafter designated xe2x80x9cimage Axe2x80x9d and xe2x80x9cimage Bxe2x80x9d) which avoids both of the artifacts described above; namely, noticeable bands at the overlap regions due to different lighting conditions in adjacent images, and ghosting due to misalignment. This approach preferably involves four stages of image processing.
A first stage is that of aligning the two images so as to register them as best as possible in the overlap region. This stage is not addressed in the present invention. Rather, the present invention relates to the image processing after the alignment is performed, using any conventional method.
A second stage involves vertical image warping, specially constructed so as to eliminate any vertical misalignment between the two images. Optimal vertical distortions for image A are calculated along selected vertical lines within the overlap region so as to minimize vertical mis-match with respect to image B. In between and outside of these selected vertical lines, the vertical distortions are filled in by linear interpolation. The result is a two-dimensional vertical distortion map for image A which brings it into vertical alignment with image B.
A third stage uses the information in the overlap region to correct the color of the two images, prior to carrying out the feathering. Popular belief tends to support the idea that the best way to take pictures with a camera in order to stitch them together, is to minimize the overlap between them, so that they can be stitched together end-to-end. On the contrary, the present invention builds upon information in the overlap region to correct the color in each of the images, in order to bring both images to equivalent lighting conditions. Thus the larger is the overlap region, the more of an information base is available for the color correction.
Once the images are color corrected, their variation due to different lighting conditions is reduced, and as a result the feathering is smoother. Even if conventional xe2x80x9cfeatheringxe2x80x9d is used, the banding artifact is significantly reduced. The present invention tapers the color correction, so that full color correction is applied within the overlap region, and outside the overlap region only a fraction of the correction is applied, where the fraction preferably tapers from 100% to 0% as the pixel distance from the overlap region increases. Normally, the color correction is not applied at all for pixels sufficiently far away from the overlap region.
A fourth stage involves a new form of feathering, which varies the relative weights of the A and B image pixels along a multitude of horizontal lines, from a value above 50% of A and a value below 50% of B at a left endpoint to 50% of A and 50% of B at a middle point, to a value below 50% of A and a value above 50% of B at a right endpoint. The horizontal lines cover the entire overlap region, from the top to the bottom.
Three control points are defined for each horizontal linexe2x80x94left endpoint, middle point and right endpoint. The locations of these points typically vary from one horizontal line to the next. The collection of left endpoints forms a downward running curve, designated as the xe2x80x9cleftmost curve,xe2x80x9d the collection of middle points forms a downward running curve, designated as the xe2x80x9cmiddle curve,xe2x80x9d and the collection of right endpoints forms a downward running curve, designated as the xe2x80x9crightmost curve.xe2x80x9d The region between the leftmost and rightmost curves becomes the xe2x80x9cfeathering region.xe2x80x9d Whereas in conventional feathering the feathering region is precisely the overlap region, which is rectangular, in the current invention the feathering region is typically non-rectangular, and lies strictly within the overlap region.
The present invention avoids ghosting by approximately aligning the two images, and then carefully choosing the leftmost and rightmost curves, so that the feathering region is as large as possible, but without containing any pixels where the two images are significantly misaligned. Misalignment can be recognized by the difference between image A and image B in the overlap region. Large differences in any of the color values indicate significant misalignment. Precisely, specific threshold values are used to indicate whether or not misalignment is xe2x80x9csignificant.xe2x80x9d
The present invention preferably first seeks a middle curve which travels downward from top to bottom, without passing through any pixels where the images are significantly misaligned. After the middle curve is found, the present invention seeks outward horizontally, left and right, from each point on the middle curve, to find the extent for which there is no significant misalignment. The limits of these extents are taken as initial candidates for the leftmost and rightmost curves. These candidate curves can be very erratic curves, and can be subsequently smoothed.
There is thus provided in accordance with a preferred embodiment of the present invention a method for compositing two digital images which overlap in an overlapping pixel region, including adjusting the pixel color values of at least one of the overlapping images, so as to produce resulting digital images including at least one modified digital image, and combining the resulting digital images in the overlapping pixel region by taking weighted averages of their pixel color values.
Additionally in accordance with a preferred embodiment of the present invention the adjusting step adjusts the pixel color values of at least one of the digital images in a pixel region which includes the overlapping pixel region.
Moreover in accordance with a preferred embodiment of the present invention the adjusting step adjusts the pixel color values of at least one of the digital images in a pixel region which includes pixels outside the overlapping region.
Further in accordance with a preferred embodiment of the present invention the pixel color values are in RGB three-channel format, and the adjusting step is applied to at least one color channel.
Still further in accordance with a preferred embodiment of the present invention the adjusting step includes modifying brightness, contrast and gamma factors of each of the digital images so as to produce modified brightness, contrast and gamma factors, denoted by xcex1, xcex2 and xcex3, respectively; and applying the modified brightness, contrast and gamma factors by changing the color intensity, denoted by I, of at least one of the digital images to a modified color intensity, denoted by Ixe2x80x2, according to the formula
Ixe2x80x2=xcex1+xcex2xc2x7Ixcex3.
Additionally in accordance with a preferred embodiment of the present invention the applying step includes constructing a lookup table which tabulates the changes in color intensity xcex94I=Ixe2x80x2xe2x88x92I indexed by I, and accessing the look-up table to modify the color intensities.
Moreover in accordance with a preferred embodiment of the present invention the changes in brightness, contrast and gamma factors produced by the applying step are applied with a weighting factor, the weighting factor tapering off from a value above 50% to a value below 50% over a pixel region outside of and adjacent to the overlapping pixel region.
There is also provided in accordance with a preferred embodiment of the present invention a method for feathering two digital images which overlap in an overlapping pixel region, including aligning the digital images so as to approximately register them in the overlapping pixel region, determining three curves, one of which is a leftmost curve, another of which is a middle curve and another of which is a rightmost curve, and at least one of which is not a straight vertical line, the curves extending from the top to the bottom of the overlapping pixel region and lying within the overlapping pixel region, and the middle curve lying between the leftmost and rightmost curves, and combining the digital images by taking a weighted average of the pixel color values, in such a way that the weights used are a value above 50% of image A and a value below 50% of image B to the left of the leftmost curve, 50% of image A and 50% of image B along the middle curve, and a value below 50% of image A and a value above 50% of image B to the right of the rightmost curve.
Further in accordance with a preferred embodiment of the present invention the middle curve is halfway between the leftmost and rightmost curves.
Still further in accordance with a preferred embodiment of the present invention the middle curve is determined in such a way so as to avoid its passing through any portion of the overlapping pixel region where there is substantial misalignment between the digital images.
Additionally in accordance with a preferred embodiment of the present invention the middle curve is determined by using an optimization algorithm, generally optimized so as to have the least amount of misalignment between the digital images along its path.
Moreover in accordance with a preferred embodiment of the present invention the optimization algorithm used is a dynamic programming algorithm.
Further in accordance with a preferred embodiment of the present invention the leftmost and rightmost curves are determined by delineating a pixel zone surrounding the middle curve wherein there is no substantial misalignment between the digital images, determining the leftmost and rightmost curves in such a way so as to be as far away as possible from the middle curve, yet remaining within the pixel zone.
Still further in accordance with a preferred embodiment of the present invention the pixel zone is delineated to be as wide as possible, without containing any pixels where there is substantial misalignment between the digital images.
Additionally in accordance with a preferred embodiment of the present invention the leftmost and rightmost curves are determined by using optimization algorithms, optimized so as to be smooth and as far away as possible from the middle curve.
Moreover in accordance with a preferred embodiment of the present invention the optimization algorithms used are dynamic programming algorithms.
There is also provided in accordance with a preferred embodiment of the present invention a method for aligning a first digital image with a second digital image which overlaps with it in an overlapping pixel region, including determining a two-dimensional table of pixel displacements for each pixel location in the first image, and replacing the color values in the first image at each source pixel location in the first image with the color value of the pixel displaced from the source pixel location by the pixel displacement for the source pixel location.
Moreover in accordance with a preferred embodiment of the present invention the pixel displacements are constrained to be zero at at least one side of the first image.
Additionally in accordance with a preferred embodiment of the present invention the pixel displacements are vertical displacements.
Further in accordance with a preferred embodiment of the present invention the determining step includes calculating pixel displacements along multiple vertical lines of pixel locations within the overlapping pixel region, and interpolating horizontally to calculate pixel displacements at pixel locations not situated on the vertical lines.
Still further in accordance with a preferred embodiment of the present invention the pixel displacements are calculated along each of the multiple vertical lines by using a dynamic programming optimization algorithm.
There is also provided in accordance with a preferred embodiment of the present invention a system for composition of digital images which overlap in an overlapping pixel region, including a digital color processor adjusting the pixel color values of at least one of the digital images, so as to produce resulting digital images including at least one modified digital image, and a pixel processor combining the resulting digital images in the overlapping pixel region by taking weighted averages of their pixel color values.
Additionally in accordance with a preferred embodiment of the present invention the digital color processor adjusts the pixel color values of at least one of the digital images in a pixel region which includes the overlapping pixel region.
Moreover in accordance with a preferred embodiment of the present invention the digital color processor adjusts the pixel color values of at least one of the digital images in a pixel region which includes pixels outside the overlapping region.
Further in accordance with a preferred embodiment of the present invention the pixel color values are in RGB three-channel format, and the digital color processor operates on at least one channel.
Still further in accordance with a preferred embodiment of the present invention the digital color processor includes a color parameter processor modifying brightness, contrast and gamma factors of each of the digital images so as to produce modified brightness, contrast and gamma factors, denoted by xcex1, xcex2 and xcex3, respectively, and an image processor applying the modified brightness, contrast and gamma factors by changing the color intensity, denoted by I, of at least one of the digital images to a modified color intensity, denoted by Ixe2x80x2, according to the formula
Ixe2x80x2=xcex1+xcex2xc2x7Ixcex3.
Additionally in accordance with a preferred embodiment of the present invention the image processor includes a calculator constructing a lookup table which tabulates the changes in color intensity xcex94I=Ixe2x80x2xe2x88x92I indexed by I, and a data retriever accessing the lookup table to modify the color intensities.
Moreover in accordance with a preferred embodiment of the present invention the changes in brightness, contrast and gamma factors produced by the color parameter processor are applied with a weighting factor, the weighting factor tapering off from a value above 50% to a value below 50% over a pixel region outside of and adjacent to the overlapping pixel region.
There is also provided in accordance with a preferred embodiment of the present invention a system for feathering two digital images which overlap in an overlapping pixel region, including a digital image aligner aligning the digital images so as to approximately register them in the overlapping pixel region, an image processor determining three curves, one of which is a leftmost curve, another of which is a middle curve and another of which is a rightmost curve, and at least one of which is not a straight vertical line, the curves extending from the top to the bottom of the overlapping pixel region and lying within the overlapping pixel region, and the middle curve lying between the leftmost and rightmost curves, and a pixel processor combining the digital images by taking a weighted average of the pixel color values, in such a way that the weights used are a value above 50% of image A and a value below 50% of image B to the left of the leftmost curve, 50% of image A and 50% of image B along the middle curve, and a value below 50% of image A and a value above 50% of image B to the right of the rightmost curve.
Further in accordance with a preferred embodiment of the present invention the middle curve is halfway between the leftmost and rightmost curves.
Still further in accordance with a preferred embodiment of the present invention the middle curve is determined by the image processor in such a way so as to avoid its passing through any portion of the overlapping pixel region where there is substantial misalignment between the digital images.
Additionally in accordance with a preferred embodiment of the present invention the middle curve is determined by the image processor by using an optimization algorithm, generally optimized so as to have the least amount of misalignment between the digital images along its path.
Moreover in accordance with a preferred embodiment of the present invention the optimization algorithm used is a dynamic programming algorithm.
Further in accordance with a preferred embodiment of the present invention the image processor determining the leftmost and rightmost curves includes a zone processor delineating a pixel zone surrounding the middle curve wherein there is no substantial misalignment between the digital images, and a curve processor determining the leftmost and rightmost curves in such a way so as to be as far away as possible from the middle curve, yet remaining within the pixel zone.
Still further in accordance with a preferred embodiment of the present invention the zone processor delineates the pixel zone in such as way so as to make it as wide as possible, substantially without containing any pixels where there is substantial misalignment between the digital images.
Additionally in accordance with a preferred embodiment of the present invention the curve processor determines the leftmost and rightmost curves by using optimization algorithms, optimized so as to make the curves smooth and as far away as possible from the middle curve.
Moreover in accordance with a preferred embodiment of the present invention the optimization algorithms used are dynamic programming algorithms.
There is also provided in accordance with a preferred embodiment of the present invention a system for aligning a first digital image with a second digital image which overlaps with it in an overlapping pixel region, including a processor determining a two-dimensional table of pixel displacements for each pixel location in the first image, and an image writer replacing the color values in the first image at each source pixel location in the first image with the color value of the pixel displaced from the source pixel location by the pixel displacement for the source pixel location.
Moreover in accordance with a preferred embodiment of the present invention the pixel displacements are constrained to be zero at at least one side of the first image.
Additionally in accordance with a preferred embodiment of the present invention the pixel displacements are vertical displacements.
Further in accordance with a preferred embodiment of the present invention the processor includes a calculator calculating pixel displacements along multiple vertical lines of pixel locations within the overlapping pixel region, and an interpolator interpolating horizontally to calculate pixel displacements at pixel locations not situated on the vertical lines.
Still further in accordance with a preferred embodiment of the present invention the calculator operates by using a dynamic programming optimization algorithm.
Throughout the specification and claims, positional and directional terms such as up, down, right, left, top and bottom have been used for the purpose of explaining relationships between various images and portions thereof. It is to be appreciated that these terms are to be considered as being relative only and that, for example top and bottom refers equally to right and left and that the present invention is not limited by the relative positions or directions of images, portions of images, curves or lines constructed thereon. For example, images may be stitched together vertically rather than horizontally as described in the specification.